package uglyNumber;

import java.util.stream.IntStream;

/**
 * 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 * 我自己设想，应该会有一个公式来表示第 k 个臭数和 k 关系。如下:
 * Ak = p2^x*3^y*5^z ;
 * 这个公式太多的常量。
 * 转化一下思想，我可以猜想一下每个臭数的距离。
 * 2  3 2*2=4 5 2*3=6 8
 * 这种题目和兔子数列类似。是前面的元素决定了后面的元素。
 * ______________
 * | x | y | z | K
 * --------------
 * 我想求 K ， K　的来源一定是从前面的　ｘ　ｙ　ｚ　这三个数据种选择一个看它他们与 2 3 5 的乘积，那一个小就是那个
 * */
public class Solution{
    public int findUglyNumber(int k ){
        int[] rs = new int[k];
        rs[0] = 1;
        int p2 = 0,p3 =0,p5 = 0 ;
        for(int i = 1 ; i < k ; i++){
            rs[i] = Math.min(rs[p2]*2,Math.min(rs[p3]*3,rs[p5]*5));
            if(rs[i] == rs[p2]*2){
                p2 = i ;
            }

            if(rs[i] == rs[p3]*3){
                p3 = i ;
            }

            if(rs[i] == rs[p5]*5){
                p5 = i ;
            }
        }
        return rs[k-1];
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        IntStream.range(1,10).forEach(i->{
            System.out.println(s.findUglyNumber(i));
        });
    }
}
